package com.yanceysong.codetop.s1_s10;

import com.yanceysong.common.ListNode;
import com.yanceysong.common.util.NodePrintUtil;

/**
 * @ClassName S9_Easy_21_合并两个有序链表
 * @Description
 * @date 2025/8/17 22:05
 * @Author yanceysong
 * @Version 1.0
 */
public class S9_Easy_21_合并两个有序链表 {
    /**
     * LeetCode:
     * <a href="https://leetcode.cn/problems/merge-two-sorted-lists/description/">...</a>
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     * 示例 2：
     * <p>
     * 输入：l1 = [], l2 = []
     * 输出：[]
     * 示例 3：
     * <p>
     * 输入：l1 = [], l2 = [0]
     * 输出：[0]
     * <p>
     * 提示：
     * <p>
     * 两个链表的节点数目范围是 [0, 50]
     * -100 <= Node.val <= 100
     * l1 和 l2 均按 非递减顺序 排列
     * <p>
     * ==================== 算法图解 ====================
     * <p>
     * 算法思路：使用双指针 + 虚拟头节点
     * 1. 创建虚拟头节点，避免边界判断
     * 2. 用两个指针分别遍历两个链表
     * 3. 比较节点值，选择较小的节点连接到结果链表
     * 4. 移动对应指针，重复比较过程
     * 5. 处理剩余节点，返回结果
     * <p>
     * 执行示例：node1=[1,2,4], node2=[1,3,4]
     * <p>
     * 初始状态：
     * first:  1 -> 2 -> 4 -> null
     * second: 1 -> 3 -> 4 -> null
     * result: dummy -> null
     * <p>
     * 第1步：比较 1 <= 1，选择first
     * first:  2 -> 4 -> null
     * second: 1 -> 3 -> 4 -> null
     * result: dummy -> 1 -> null
     * <p>
     * 第2步：比较 2 > 1，选择second
     * first:  2 -> 4 -> null
     * second: 3 -> 4 -> null
     * result: dummy -> 1 -> 1 -> null
     * <p>
     * 第3步：比较 2 <= 3，选择first
     * first:  4 -> null
     * second: 3 -> 4 -> null
     * result: dummy -> 1 -> 1 -> 2 -> null
     * <p>
     * 第4步：比较 4 > 3，选择second
     * first:  4 -> null
     * second: 4 -> null
     * result: dummy -> 1 -> 1 -> 2 -> 3 -> null
     * <p>
     * 第5步：比较 4 <= 4，选择first
     * first:  null
     * second: 4 -> null
     * result: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> null
     * <p>
     * 第6步：first为null，连接剩余的second
     * result: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null
     * <p>
     * 最终返回：result.next = [1,1,2,3,4,4]
     * <p>
     * 时间复杂度：O(m + n)，其中m和n分别是两个链表的长度
     * 空间复杂度：O(1)，只使用了常数个额外变量
     * <p>
     * 关键点：
     * - 虚拟头节点简化边界处理
     * - 双指针确保每个节点只访问一次
     * - 利用链表已排序的特性，贪心选择较小值
     * - 最后连接剩余节点，无需继续比较
     * <p>
     * ================================================
     */
    public ListNode mergeTwoLists(ListNode node1, ListNode node2) {
        // 步骤1：初始化双指针，分别指向两个链表的头节点
        ListNode first = node1;   // 指向第一个链表的当前节点
        ListNode second = node2;  // 指向第二个链表的当前节点

        // 步骤2：创建虚拟头节点，简化边界处理
        ListNode newListNode = new ListNode();  // 虚拟头节点
        ListNode result = newListNode;           // 保存虚拟头节点的引用

        // 步骤3：双指针遍历，比较节点值并构建结果链表
        while (first != null && second != null) {
            if (first.val <= second.val) {
                // 第一个链表的当前节点值较小或相等，选择它
                newListNode.next = first;    // 连接到结果链表
                first = first.next;          // 第一个链表指针后移
            } else {
                // 第二个链表的当前节点值较小，选择它
                newListNode.next = second;   // 连接到结果链表
                second = second.next;        // 第二个链表指针后移
            }
            newListNode = newListNode.next;  // 结果链表指针后移
        }

        // 步骤4：连接剩余节点（必有一个链表已遍历完）
        // 将未遍历完的链表剩余部分直接连接到结果链表末尾
        newListNode.next = first != null ? first : second;

        // 步骤5：返回真正的头节点（跳过虚拟头节点）
        return result.next;
    }

    public static void main(String[] args) {
        S9_Easy_21_合并两个有序链表 solution = new S9_Easy_21_合并两个有序链表();

        System.out.println("=== 合并两个有序链表测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同长度链表测试
        System.out.println("\n--- 测试3: 不同长度链表测试 ---");
        testDifferentLengths(solution);

        // 测试4: 特殊值测试
        System.out.println("\n--- 测试4: 特殊值测试 ---");
        testSpecialValues(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        // 额外验证：合并正确性
        verifyMergeCorrectness();

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 创建链表的辅助方法
     *
     * @param values 节点值数组
     * @return 链表头节点
     */
    private static ListNode createList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }

        ListNode head = new ListNode(values[0]);
        ListNode current = head;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }

        return head;
    }

    /**
     * 将链表转换为数组的辅助方法
     *
     * @param head 链表头节点
     * @return 节点值数组
     */
    private static int[] listToArray(ListNode head) {
        if (head == null) {
            return new int[0];
        }

        // 先计算链表长度
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        // 转换为数组
        int[] result = new int[length];
        current = head;
        for (int i = 0; i < length; i++) {
            result[i] = current.val;
            current = current.next;
        }

        return result;
    }

    /**
     * 打印数组的辅助方法
     */
    private static void printArray(int[] arr) {
        if (arr.length == 0) {
            System.out.print("[]");
            return;
        }

        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(",");
            }
        }
        System.out.print("]");
    }

    /**
     * 验证链表是否有序的辅助方法
     */
    private static boolean isListSorted(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode current = head;
        while (current.next != null) {
            if (current.val > current.next.val) {
                return false;
            }
            current = current.next;
        }
        return true;
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S9_Easy_21_合并两个有序链表 solution) {
        // 示例1: [1,2,4] + [1,3,4] = [1,1,2,3,4,4]
        int[] list1_1 = {1, 2, 4};
        int[] list2_1 = {1, 3, 4};
        int[] expected1 = {1, 1, 2, 3, 4, 4};

        ListNode l1 = createList(list1_1);
        ListNode l2 = createList(list2_1);
        ListNode result1 = solution.mergeTwoLists(l1, l2);
        int[] actual1 = listToArray(result1);

        System.out.print("输入: list1=");
        printArray(list1_1);
        System.out.print(", list2=");
        printArray(list2_1);
        System.out.print(" -> 输出: ");
        printArray(actual1);
        System.out.print(" (期望: ");
        printArray(expected1);
        System.out.println(")");

        assert java.util.Arrays.equals(actual1, expected1) : "示例1测试失败";
        assert isListSorted(result1) : "示例1：结果链表应该是有序的";

        // 示例2: [] + [] = []
        ListNode result2 = solution.mergeTwoLists(null, null);
        int[] actual2 = listToArray(result2);

        System.out.print("输入: list1=[], list2=[] -> 输出: ");
        printArray(actual2);
        System.out.println(" (期望: [])");

        assert actual2.length == 0 : "示例2测试失败";

        // 示例3: [] + [0] = [0]
        int[] list2_3 = {0};
        int[] expected3 = {0};

        ListNode l2_3 = createList(list2_3);
        ListNode result3 = solution.mergeTwoLists(null, l2_3);
        int[] actual3 = listToArray(result3);

        System.out.print("输入: list1=[], list2=");
        printArray(list2_3);
        System.out.print(" -> 输出: ");
        printArray(actual3);
        System.out.print(" (期望: ");
        printArray(expected3);
        System.out.println(")");

        assert java.util.Arrays.equals(actual3, expected3) : "示例3测试失败";
        assert isListSorted(result3) : "示例3：结果链表应该是有序的";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S9_Easy_21_合并两个有序链表 solution) {
        // 测试1: 两个空链表
        ListNode result1 = solution.mergeTwoLists(null, null);
        System.out.println("两个空链表: null + null -> " + (result1 == null ? "null" : "非null") + " (期望: null)");
        assert result1 == null : "两个空链表测试失败";

        // 测试2: 第一个链表为空
        int[] list2_2 = {1, 2, 3};
        int[] expected2 = {1, 2, 3};

        ListNode l2_2 = createList(list2_2);
        ListNode result2 = solution.mergeTwoLists(null, l2_2);
        int[] actual2 = listToArray(result2);

        System.out.print("第一个链表为空: null + ");
        printArray(list2_2);
        System.out.print(" -> ");
        printArray(actual2);
        System.out.print(" (期望: ");
        printArray(expected2);
        System.out.println(")");

        assert java.util.Arrays.equals(actual2, expected2) : "第一个链表为空测试失败";
        assert isListSorted(result2) : "第一个链表为空：结果应该有序";

        // 测试3: 第二个链表为空
        int[] list1_3 = {4, 5, 6};
        int[] expected3 = {4, 5, 6};

        ListNode l1_3 = createList(list1_3);
        ListNode result3 = solution.mergeTwoLists(l1_3, null);
        int[] actual3 = listToArray(result3);

        System.out.print("第二个链表为空: ");
        printArray(list1_3);
        System.out.print(" + null -> ");
        printArray(actual3);
        System.out.print(" (期望: ");
        printArray(expected3);
        System.out.println(")");

        assert java.util.Arrays.equals(actual3, expected3) : "第二个链表为空测试失败";
        assert isListSorted(result3) : "第二个链表为空：结果应该有序";

        // 测试4: 单节点链表
        int[] list1_4 = {1};
        int[] list2_4 = {2};
        int[] expected4 = {1, 2};

        ListNode l1_4 = createList(list1_4);
        ListNode l2_4 = createList(list2_4);
        ListNode result4 = solution.mergeTwoLists(l1_4, l2_4);
        int[] actual4 = listToArray(result4);

        System.out.print("单节点链表: ");
        printArray(list1_4);
        System.out.print(" + ");
        printArray(list2_4);
        System.out.print(" -> ");
        printArray(actual4);
        System.out.print(" (期望: ");
        printArray(expected4);
        System.out.println(")");

        assert java.util.Arrays.equals(actual4, expected4) : "单节点链表测试失败";
        assert isListSorted(result4) : "单节点链表：结果应该有序";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同长度的链表
     */
    private static void testDifferentLengths(S9_Easy_21_合并两个有序链表 solution) {
        // 测试1: 长度差异很大 [1] + [2,3,4,5,6]
        int[] list1_1 = {1};
        int[] list2_1 = {2, 3, 4, 5, 6};
        int[] expected1 = {1, 2, 3, 4, 5, 6};
        testMergeCase(solution, list1_1, list2_1, expected1, "短链表+长链表");

        // 测试2: 长度差异很大 [1,2,3,4,5] + [6]
        int[] list1_2 = {1, 2, 3, 4, 5};
        int[] list2_2 = {6};
        int[] expected2 = {1, 2, 3, 4, 5, 6};
        testMergeCase(solution, list1_2, list2_2, expected2, "长链表+短链表");

        // 测试3: 交错合并 [1,3,5] + [2,4,6,7,8]
        int[] list1_3 = {1, 3, 5};
        int[] list2_3 = {2, 4, 6, 7, 8};
        int[] expected3 = {1, 2, 3, 4, 5, 6, 7, 8};
        testMergeCase(solution, list1_3, list2_3, expected3, "交错合并");

        // 测试4: 第一个链表所有元素都小 [1,2,3] + [4,5,6]
        int[] list1_4 = {1, 2, 3};
        int[] list2_4 = {4, 5, 6};
        int[] expected4 = {1, 2, 3, 4, 5, 6};
        testMergeCase(solution, list1_4, list2_4, expected4, "第一个链表都小");

        // 测试5: 第二个链表所有元素都小 [4,5,6] + [1,2,3]
        int[] list1_5 = {4, 5, 6};
        int[] list2_5 = {1, 2, 3};
        int[] expected5 = {1, 2, 3, 4, 5, 6};
        testMergeCase(solution, list1_5, list2_5, expected5, "第二个链表都小");

        System.out.println("✓ 不同长度链表测试通过");
    }

    /**
     * 辅助方法：测试合并情况
     */
    private static void testMergeCase(S9_Easy_21_合并两个有序链表 solution,
                                      int[] list1, int[] list2, int[] expected, String description) {
        ListNode l1 = createList(list1);
        ListNode l2 = createList(list2);
        ListNode result = solution.mergeTwoLists(l1, l2);
        int[] actual = listToArray(result);

        System.out.print(description + " - ");
        printArray(list1);
        System.out.print(" + ");
        printArray(list2);
        System.out.print(" -> ");
        printArray(actual);
        System.out.print(" (期望: ");
        printArray(expected);
        System.out.println(")");

        assert java.util.Arrays.equals(actual, expected) : description + "测试失败";
        assert isListSorted(result) : description + "：结果应该有序";
    }

    /**
     * 测试特殊值
     */
    private static void testSpecialValues(S9_Easy_21_合并两个有序链表 solution) {
        // 测试1: 包含负数 [-3,-1,0] + [-2,1,2]
        int[] list1_1 = {-3, -1, 0};
        int[] list2_1 = {-2, 1, 2};
        int[] expected1 = {-3, -2, -1, 0, 1, 2};
        testMergeCase(solution, list1_1, list2_1, expected1, "包含负数");

        // 测试2: 全负数 [-5,-3,-1] + [-4,-2,0]
        int[] list1_2 = {-5, -3, -1};
        int[] list2_2 = {-4, -2, 0};
        int[] expected2 = {-5, -4, -3, -2, -1, 0};
        testMergeCase(solution, list1_2, list2_2, expected2, "全负数");

        // 测试3: 相同元素 [1,2,3] + [1,2,3]
        int[] list1_3 = {1, 2, 3};
        int[] list2_3 = {1, 2, 3};
        int[] expected3 = {1, 1, 2, 2, 3, 3};
        testMergeCase(solution, list1_3, list2_3, expected3, "相同元素");

        // 测试4: 大量重复 [1,1,1] + [1,1,1]
        int[] list1_4 = {1, 1, 1};
        int[] list2_4 = {1, 1, 1};
        int[] expected4 = {1, 1, 1, 1, 1, 1};
        testMergeCase(solution, list1_4, list2_4, expected4, "大量重复");

        // 测试5: 极值 [-100,-50,0] + [50,100]
        int[] list1_5 = {-100, -50, 0};
        int[] list2_5 = {50, 100};
        int[] expected5 = {-100, -50, 0, 50, 100};
        testMergeCase(solution, list1_5, list2_5, expected5, "极值测试");

        // 测试6: 单个元素重复 [0] + [0]
        int[] list1_6 = {0};
        int[] list2_6 = {0};
        int[] expected6 = {0, 0};
        testMergeCase(solution, list1_6, list2_6, expected6, "单个元素重复");

        System.out.println("✓ 特殊值测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S9_Easy_21_合并两个有序链表 solution) {
        // 测试1: 中等长度链表 (25个节点)
        System.out.println("性能测试1: 25个节点");
        testPerformanceCase(solution, 25);

        // 测试2: 较长链表 (50个节点 - 题目限制的最大值)
        System.out.println("性能测试2: 50个节点");
        testPerformanceCase(solution, 50);

        // 测试3: 最坏情况 - 交替合并
        System.out.println("性能测试3: 最坏情况 - 交替合并");
        testWorstCasePerformance(solution);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S9_Easy_21_合并两个有序链表 solution, int maxSize) {
        // 创建两个有序链表
        int[] list1 = new int[maxSize];
        int[] list2 = new int[maxSize];

        // 第一个链表：偶数
        for (int i = 0; i < maxSize; i++) {
            list1[i] = i * 2;
        }

        // 第二个链表：奇数
        for (int i = 0; i < maxSize; i++) {
            list2[i] = i * 2 + 1;
        }

        ListNode l1 = createList(list1);
        ListNode l2 = createList(list2);

        long startTime = System.currentTimeMillis();
        ListNode result = solution.mergeTwoLists(l1, l2);
        long endTime = System.currentTimeMillis();

        // 验证结果正确性
        assert isListSorted(result) : "性能测试：结果应该有序";

        int[] resultArray = listToArray(result);
        assert resultArray.length == maxSize * 2 : "性能测试：结果长度应该是两个链表长度之和";

        System.out.println("  链表长度: " + maxSize + " + " + maxSize +
                           ", 结果长度: " + resultArray.length +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        // 验证时间复杂度为O(m+n)，应该很快完成
        assert (endTime - startTime) < 100 : "性能测试：执行时间过长，可能存在性能问题";
    }

    /**
     * 辅助方法：最坏情况性能测试
     */
    private static void testWorstCasePerformance(S9_Easy_21_合并两个有序链表 solution) {
        // 创建交替合并的最坏情况
        int[] list1 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25};
        int[] list2 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26};
        int[] expected = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26};

        ListNode l1 = createList(list1);
        ListNode l2 = createList(list2);

        long startTime = System.currentTimeMillis();
        ListNode result = solution.mergeTwoLists(l1, l2);
        long endTime = System.currentTimeMillis();

        int[] actual = listToArray(result);

        // 验证结果正确性
        assert java.util.Arrays.equals(actual, expected) : "最坏情况：结果不正确";
        assert isListSorted(result) : "最坏情况：结果应该有序";

        System.out.println("  最坏情况测试 - 链表长度: " + list1.length + " + " + list2.length +
                           ", 结果长度: " + actual.length +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        assert (endTime - startTime) < 50 : "最坏情况：执行时间过长";
    }

    /**
     * 额外验证：验证合并的正确性
     */
    private static void verifyMergeCorrectness() {
        System.out.println("\n--- 额外验证：合并正确性 ---");
        S9_Easy_21_合并两个有序链表 solution = new S9_Easy_21_合并两个有序链表();

        // 创建测试链表
        int[] list1 = {1, 3, 5};
        int[] list2 = {2, 4, 6};

        ListNode l1 = createList(list1);
        ListNode l2 = createList(list2);

        System.out.println("原链表1结构验证:");
        NodePrintUtil.printListNodeWithDescription(l1, "链表1");

        System.out.println("原链表2结构验证:");
        NodePrintUtil.printListNodeWithDescription(l2, "链表2");

        // 合并链表
        ListNode merged = solution.mergeTwoLists(l1, l2);

        System.out.println("合并后链表结构验证:");
        NodePrintUtil.printListNodeWithDescription(merged, "合并链表");

        // 验证合并结果
        int[] expected = {1, 2, 3, 4, 5, 6};
        int[] actual = listToArray(merged);

        assert java.util.Arrays.equals(actual, expected) : "合并正确性验证失败";
        assert isListSorted(merged) : "合并结果应该有序";

        System.out.println("✓ 合并正确性验证通过");
    }
}
